home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 135_01 / prime.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-03-09  |  1.8 KB  |  95 lines
  1. /*
  2.     prime.c---random prime number generator.  This program
  3.     uses Algorithm P(Probabilistic primality test).  From
  4.     "Seminumerical Algorithms: The Art of Computer Programming",
  5.     Vol. 2, by D. E. Knuth, page 379. This version for BDSc...
  6.  
  7.     by Hugh S. Myers
  8.  
  9.     build:
  10.         n>cc prime
  11.         n>clink prime ratc vli math
  12.  
  13.     3/17/84
  14.     4/9/84
  15. */
  16.  
  17. #include <bdscio.h>
  18. #define MAX 256
  19.  
  20. main()
  21. {
  22.     char n[MAX], limit[MAX];
  23.     int i, p;
  24.  
  25.     puts("prime.c a random prime number generator\n");
  26.     while(i<1 || i>100) {
  27.         puts("number of digits to start with (for 0 < n < 100)? ");
  28.         getline(n,MAX);
  29.         i=atoi(n);
  30.     }
  31.     strcpy(n,randl(0));
  32.     while(strlen(n)<i)
  33.         strcat(n,randl(0));
  34.     strcpy(limit,"1");
  35.     pad(limit,i);
  36.     strcpy(n,modl(n,limit));
  37.     if(iseven(n))
  38.         strcpy(n,incrl(n));
  39.     forever {
  40.         puts(n);
  41.         for(i=0;i<10;i++) {
  42.             p=primal(n);
  43.             if(!p)
  44.                 break;
  45.         }
  46.         if(p) {
  47.             puts(" is prime\n");
  48.         }
  49.         else
  50.             puts(" is not prime\n");
  51.         strcpy(n,saddl(n,2));
  52.     }
  53. }
  54.  
  55. int primal(n)
  56. char *n;
  57. {
  58.     char k[MAX], q[MAX], y[MAX], x[MAX], j[MAX], n1[MAX];
  59.     int i;    
  60. /*
  61.     do the easy ones first
  62. */
  63.     i=qprime(n);
  64.     if(!i)
  65.         return FALSE;
  66.     if(i==1)
  67.         return TRUE;
  68. /*
  69.     now do it the hard way
  70. */
  71.     strcpy(n1,decrl(n));
  72.     strcpy(q,n1);
  73.     strcpy(k,"0");
  74.     while(iseven(q)) {
  75.         strcpy(q,sdivl(q,2));
  76.         strcpy(k,incrl(k));
  77.     }
  78.     strcpy(j,"0");
  79.     do {
  80.         strcpy(x,randl(0));
  81.         strcpy(x,modl(x,n));
  82.     } while (strcmp(x,"2") < 0);
  83.     strcpy(y,modp(x,q,n));
  84.     forever {
  85.         if((iszero(j) && sisequal(y,1)) || isequal(y,n1))
  86.             return TRUE;
  87.         if(!iszero(j) && sisequal(y,1))
  88.             return FALSE;
  89.         strcpy(j,incrl(j));
  90.         if(strcmp(j,k) < 0)
  91.             strcpy(y,modp(y,"2",n));
  92.         else
  93.             return FALSE;
  94.     }
  95. }